class HashTableAlgorithm:
    @staticmethod
    def two_sum(nums, target):
        """
        两数之和算法

        参数:
        nums (List[int]): 输入的数组
        target (int): 目标和

        返回:
        List[int]: 包含两个数的索引列表

        实现步骤:
        1. 创建一个字典用于存储数组元素和其索引的映射关系
        2. 遍历数组，对于每个元素，计算目标和与当前元素的差值
        3. 如果差值在字典中存在，则返回差值对应的索引和当前元素的索引
        4. 如果差值不在字典中，将当前元素和其索引添加到字典中

        """

        # 步骤 1: 创建一个字典用于存储数组元素和其索引的映射关系
        num_dict = {}

        # 步骤 2: 遍历数组
        for i, num in enumerate(nums):
            # 步骤 3: 计算目标和与当前元素的差值
            complement = target - num

            # 步骤 4: 如果差值在字典中存在，则返回差值对应的索引和当前元素的索引
            if complement in num_dict:
                return [num_dict[complement], i]

            # 将当前元素和其索引添加到字典中
            num_dict[num] = i

        return []

    @staticmethod
    def longest_substring_without_repeating_chars(s):
        """
        无重复字符的最长子串算法

        参数:
        s (str): 输入的字符串

        返回:
        int: 最长无重复字符子串的长度

        实现步骤:
        1. 创建一个字典用于存储字符和其最后出现位置的映射关系
        2. 使用双指针维护一个滑动窗口，窗口内的字符不重复
        3. 遍历字符串，更新左指针和最长子串的长度
        4. 返回最长子串的长度

        """

        # 步骤 1: 创建一个字典用于存储字符和其最后出现位置的映射关系
        char_dict = {}

        # 步骤 2: 使用双指针维护一个滑动窗口，窗口内的字符不重复
        left = 0
        longest = 0

        # 步骤 3: 遍历字符串
        for right in range(len(s)):
            # 当前字符在窗口内重复，更新左指针位置
            if s[right] in char_dict and char_dict[s[right]] >= left:
                left = char_dict[s[right]] + 1

            # 更新字符最后出现位置
            char_dict[s[right]] = right

            # 更新最长子串的长度
            longest = max(longest, right - left + 1)

        # 步骤 4: 返回最长子串的长度
        return longest

    @staticmethod
    def group_anagrams(strs):
        """
        字母异位词分组算法

        参数:
        strs (List[str]): 输入的字符串列表

        返回:
        List[List[str]]: 分组后的字符串列表

        实现步骤:
        1. 创建一个字典用于存储异位词分组
        2. 遍历字符串列表，对每个字符串进行排序，并将排序后的字符串作为键
        3. 如果键在字典中存在，则将当前字符串添加到对应的分组中
        4. 如果键在字典中不存在，则创建一个新的分组，并将当前字符串添加到该分组中
        5. 返回所有分组的列表

        """

        # 步骤 1: 创建一个字典用于存储异位词分组
        anagram_groups = {}

        # 步骤 2: 遍历字符串列表
        for s in strs:
            # 步骤 3: 对每个字符串进行排序，并将排序后的字符串作为键
            key = "".join(sorted(s))

            # 步骤 4: 如果键在字典中存在，则将当前字符串添加到对应的分组中
            if key in anagram_groups:
                anagram_groups[key].append(s)
            # 步骤 5: 如果键在字典中不存在，则创建一个新的分组，并将当前字符串添加到该分组中
            else:
                anagram_groups[key] = [s]

        # 返回所有分组的列表
        return list(anagram_groups.values())

if __name__ == '__main__':
    # 示例调用两数之和算法
    nums = [2, 7, 11, 15]
    target = 9
    two_sum_result = HashTableAlgorithm.two_sum(nums, target)
    print("两数之和算法:")
    print("输入:", nums, target)
    print("输出:", two_sum_result)
    """
    示例输出结果:
    输入: [2, 7, 11, 15] 9
    输出: [0, 1]
    """

    # 示例调用无重复字符的最长子串算法
    s = "abcabcbb"
    longest_substring_result = HashTableAlgorithm.longest_substring_without_repeating_chars(s)
    print("无重复字符的最长子串算法:")
    print("输入:", s)
    print("输出:", longest_substring_result)
    """
    示例输出结果:
    输入: "abcabcbb"
    输出: 3
    """

    # 示例调用字母异位词分组算法
    strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    group_anagrams_result = HashTableAlgorithm.group_anagrams(strs)
    print("字母异位词分组算法:")
    print("输入:", strs)
    print("输出:", group_anagrams_result)
    """
    示例输出结果:
    输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
    输出: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
    """
